/**
 * 
 * 二叉树   前序遍历 root>>>left>>>right  中序遍历  left>>>root>>>right  后序遍历 left>>>right>>>root
 * 
 * 
 */


type TreeType = {
    value:number,
    left:TreeType | null,
    right:TreeType | null
}

const TreeData:TreeType = {
    value:4,
    left:{
        value:2,
        left:{
            value:1,
            left:null,
            right:null
        },
        right:{
            value:3,
            left:null,
            right:null
        }
    },
    right:{
        value:6,
        left:{
            value:5,
            left:null,
            right:null
        },
        right:{
            value:7,
            left:null,
            right:null
        }
    }
}


/**
 * 前序遍历
 */

const preorderTraversal = (TreeData:TreeType | null)=>{
    if(TreeData === null) return
    console.log(TreeData.value)
    preorderTraversal(TreeData.left)
    preorderTraversal(TreeData.right)
}

/**中序遍历 */
const inorderTraversal = (TreeData:TreeType | null)=>{
    if(TreeData === null) return
    inorderTraversal(TreeData.left)
    console.log(TreeData.value)
    inorderTraversal(TreeData.right)
}
/**后序遍历 */
const postorderTraversal = (TreeData:TreeType | null)=>{
    if(TreeData === null) return
    postorderTraversal(TreeData.left)
    postorderTraversal(TreeData.right)
    console.log(TreeData.value)
}


// preorderTraversal(TreeData)
// inorderTraversal(TreeData)
// postorderTraversal(TreeData)


/**
 * 
 * @description 求二叉搜索树的第K小值
 * 
 * 要满足二叉搜索树（bst）可以实现快速的查找
 *   即左边的值小于root值 right值 大于root值   这样中序遍历可以获取到 递增的数组  这样可以获取到第k的小值
 */
let arr11:number[] = []
const inorderTraversal2 = (TreeData:TreeType | null)=>{
    if(TreeData === null) return
    inorderTraversal2(TreeData.left)
    arr11.push(TreeData.value)
    inorderTraversal2(TreeData.right)
}

const BSTkVal = (TreeData:TreeType,k:number)=>{
    inorderTraversal2(TreeData)
    return arr11[k]
}

console.log(BSTkVal(TreeData,2))


/***
 * 
 * 为什么选择BST 因为 平衡二叉搜索树的增删改查的时间复杂度都是O(logN)
 * 相对于数组和链表有优势
 * 数组  增删 O(n) 查O(1)
 * 链表 增删 O(1) 查O(n)
 * 红黑树  自平衡二叉搜索树 通过颜色维持平衡
 */


